class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid[0][0]==1)return -1;

        int n=grid.size();
        int ans=1;
        const int dire[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1}}; //八个方向的

        queue<pair<int,int> > q;

        q.emplace(0,0); 

        grid[0][0]=1;   

        while(!q.empty()){      //bfs
            int m=q.size();
            while(m--){
                auto [x,y]=q.front();
                q.pop();
                if(x==n-1&&y==n-1)return ans;
                for(int i=0;i<8;i++){                       
                    int nx=x+dire[i][0];
                    int ny=y+dire[i][1];
                    if(nx<0||ny<0||nx>=n||ny>=n) continue;    
                    if(grid[nx][ny]==0){        
                        q.emplace(nx,ny);
                        grid[nx][ny]=1;         
                    }
                }
            }
            ans++;          //记录循环次数
        }
        return -1;

    }
};